1. Field of the Invention
The present invention relates to methods in the field of digital imaging, and more particularly, to reverse rendering method, such as photogrammetry and match-moving, for digital modeling.
2. Description of Related Art
In recent decades, computers have increasingly been used to generate and/or modify moving images for virtually every application that makes use of them, for example, television and motion pictures, computer games, and engineering model building. It is believed that use of digital modeling will become much more widespread in the future. Reverse-rendering methods—i.e., methods for determining what geometric, motion, lighting, camera, and other input will result in a desired image or image sequence—are likely to play an important role in developing digital models for a variety of applications.
For example, one of the problems encountered in digital modeling involves the use of photogrammetry to build three-dimensional (“3-D”) models using two-dimensional (“2-D”) photographic data. Match-moving methods extend photogrammetry to the modeling of movement over a sequence of images. Current photogrammetry and match-moving methods are difficult to implement in a flexible manner. Consequently, prior-art applications generally place undesirable constraints on acceptable input data, in order to keep complexity and programming requirements at a manageable level. For example, many prior art methods do not permit a user to specify arbitrary expressions for defining relationships between parameters of a scene graph. In addition, prior-art methods do not allow placement of the camera anywhere in the scene graph. Present methods may also sometimes become locked in a computational loop or arrive at an incorrect solution, thereby failing construct useful 3-D models from the available 2-D data at all. It is therefore desirable to provide an improved method for constructing 3-D digital models from 2-D photographic data, that overcomes the limitations of prior-art photogrammetry techniques.
Photogrammetry, match-moving, and other reverse-rendering methods may be viewed as applications for differential calculus. Differential calculus has many applications in digital movie production. For example, its applications include rendering (anti-aliasing, motion-blurring), animation (inverse-kinematics, match-moving), modeling (determination of normals, photogrammetry), simulation (implicit integration of equations of motion), and other miscellaneous applications (lens and color calibration, optical flow estimation, and others). Traditionally, differential calculus is applied to such problems by writing software to compute derivatives of functions and approximations of derivatives, such as by deriving expressions by manual analysis and implementing these as expressions in software code, by post-processing, or using finite differences.
Each of these traditional methods is subject to various limitations. Differentiating code by hand is a tedious and error-prone process, and generally makes code more difficult to modify. Post-processing of source code to automatically generate coded differential expressions complicates the programming process and constrains coding styles. Finite difference methods, which calculate an approximation of a differential using a finite difference δ, may not be sufficiently accurate. With these methods, there is some difficulty associated with selecting a proper value for δ. Too large, and the approximation will be poor. Too small, and the result may be dominated by rounding errors.
However, there is another technique: automatic differentiation. Despite extensive use of differential calculus, automatic differentiation is not well known in the digital imaging art, although some scattered references exist. It is further desirable to apply automatic differentiation to the solution of various differential calculus problems in digital imaging, for photogrammetry and other applications in a way that increases computational speed and/or lowers programming costs.